home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / libg_261.zip / libg_261 / libg++ / src / gen / List.ccP < prev    next >
Text File  |  1994-10-14  |  18KB  |  971 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1988 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.  
  6. This file is part of the GNU C++ Library.  This library is free
  7. software; you can redistribute it and/or modify it under the terms of
  8. the GNU Library General Public License as published by the Free
  9. Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.  This library is distributed in the hope
  11. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  12. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13. PURPOSE.  See the GNU Library General Public License for more details.
  14. You should have received a copy of the GNU Library General Public
  15. License along with this library; if not, write to the Free Software
  16. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  17. */
  18.  
  19. #ifdef __GNUG__
  20. #pragma implementation
  21. #endif
  22. #include <builtin.h>
  23. #include "<T>.List.h"
  24.  
  25. <T>ListNode Nil<T>ListNode;
  26.  
  27. class init_Nil<T>ListNode
  28. {
  29. public:
  30.   init_Nil<T>ListNode() 
  31.   {
  32.     Nil<T>ListNode.tl = &Nil<T>ListNode;
  33.     Nil<T>ListNode.ref = -1;
  34.   }
  35. };
  36.  
  37. static init_Nil<T>ListNode Nil<T>ListNode_initializer;
  38.  
  39. <T>List& <T>List::operator = (const <T>List& a)
  40. {
  41.   reference(a.P);
  42.   dereference(P);
  43.   P = a.P;
  44.   return *this;
  45. }
  46.  
  47. <T> <T>List::pop()
  48. {
  49.   <T> res = P->hd;
  50.   <T>ListNode* tail = P->tl;
  51.   reference(tail);
  52.   dereference(P);
  53.   P = tail;
  54.   return res;
  55. }
  56.  
  57. void <T>List::set_tail(<T>List& a)
  58. {
  59.   reference(a.P);
  60.   dereference(P->tl);
  61.   P->tl = a.P;
  62. }
  63.  
  64. <T>List <T>List::nth(int n)
  65. {
  66.   for (<T>ListNode* p = P; n-- > 0; p = p->tl);
  67.   reference(p);
  68.   return <T>List(p);
  69. }
  70.  
  71. <T>List <T>List::last()
  72. {
  73.   <T>ListNode* p = P;
  74.   if (p != &Nil<T>ListNode) while (p->tl != &Nil<T>ListNode) p = p->tl;
  75.   reference(p);
  76.   return <T>List(p);
  77. }
  78.  
  79. void <T>List::append(<T>List& l)
  80. {
  81.   <T>ListNode* p = P;
  82.   <T>ListNode* a = l.P;
  83.   reference(a);
  84.   if (p != &Nil<T>ListNode)
  85.   {
  86.     while (p->tl != &Nil<T>ListNode) p = p->tl;
  87.     p->tl = a;
  88.   }
  89.   else
  90.     P = a;
  91. }
  92.  
  93. int <T>List::length()
  94. {
  95.   int l = 0;
  96.   for (<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl) ++l;
  97.   return l;
  98. }
  99.  
  100. <T>&  <T>List::operator [] (int n)
  101. {
  102.   for (<T>ListNode* p = P; n-- > 0; p = p->tl);
  103.   return (p->hd);
  104. }
  105.  
  106. int operator == (const <T>List& x, const <T>List& y)
  107. {
  108.   <T>ListNode* a = x.P;
  109.   <T>ListNode* b = y.P;
  110.   
  111.   for (;;)
  112.   {
  113.     if (a == &Nil<T>ListNode)
  114.       return b == &Nil<T>ListNode;
  115.     else if (b == &Nil<T>ListNode)
  116.       return 0;
  117.     else if (<T>EQ(a->hd, b->hd))
  118.     {
  119.       a = a->tl;
  120.       b = b->tl;
  121.     }
  122.     else
  123.       return 0;
  124.   }
  125. }
  126.  
  127.  
  128. void <T>List::apply(<T>Procedure f)
  129. {
  130.   for(<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl)
  131.     (*f)((p->hd));
  132. }
  133.  
  134. void <T>List::subst(<T&> old, <T&> repl)
  135. {
  136.   for(<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl)
  137.     if (<T>EQ(p->hd, old))
  138.       p->hd = repl;
  139. }
  140.  
  141. <T> <T>List::reduce(<T>Combiner f, <T&> base)
  142. {
  143.   <T> r = base;
  144.   for(<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl)
  145.     r = (*f)(r, (p->hd));
  146.   return r;
  147. }
  148.  
  149. int <T>List::position(<T&> targ)
  150. {
  151.   int l = 0;
  152.   <T>ListNode* p = P;
  153.   for (;;)
  154.   {
  155.     if (p == &Nil<T>ListNode)
  156.       return -1;
  157.     else if (<T>EQ(p->hd, targ))
  158.       return l;
  159.     else
  160.     {
  161.       ++l;
  162.       p = p->tl;
  163.     }
  164.   }
  165. }
  166.  
  167. int <T>List::contains(<T&> targ)
  168. {
  169.   <T>ListNode* p = P;
  170.   for (;;)
  171.   {
  172.     if (p == &Nil<T>ListNode)
  173.       return 0;
  174.     else if (<T>EQ(p->hd, targ))
  175.       return 1;
  176.     else
  177.       p = p->tl;
  178.   }
  179. }
  180.  
  181. <T>List <T>List::find(<T&> targ)
  182. {
  183.   <T>ListNode* p = P;
  184.   while (p != &Nil<T>ListNode && !<T>EQ(p->hd, targ))
  185.     p=p->tl;
  186.   reference(p);
  187.   return <T>List(p);
  188. }
  189.  
  190. Pix <T>List::seek(<T&> targ) const
  191. {
  192.   const <T>ListNode* p = P; 
  193.   for (;;)
  194.   {
  195.     if (p == &Nil<T>ListNode)
  196.       return 0;
  197.     else if (<T>EQ(p->hd, targ))
  198.       return Pix(p);
  199.     else
  200.       p = p->tl;
  201.   }
  202. }
  203.  
  204. int <T>List::owns(Pix i)
  205. {
  206.   <T>ListNode* p = P; 
  207.   for (;;)
  208.   {
  209.     if (p == &Nil<T>ListNode)
  210.       return 0;
  211.     else if (Pix(p) == i)
  212.       return 1;
  213.     else
  214.       p = p->tl;
  215.   }
  216. }
  217.  
  218. <T>List <T>List::find(<T>List& target)
  219. {
  220.   <T>ListNode* targ = target.P;
  221.   if (targ == &Nil<T>ListNode)
  222.     return <T>List(targ);
  223.  
  224.   <T>ListNode* p = P;
  225.   while (p != &Nil<T>ListNode)
  226.   {
  227.     if (<T>EQ(p->hd, targ->hd))
  228.     {
  229.       <T>ListNode* a = p->tl;
  230.       <T>ListNode* t = targ->tl;
  231.       for(;;)
  232.       {
  233.         if (t == &Nil<T>ListNode)
  234.         {
  235.           reference(p);
  236.           return <T>List(p);
  237.         }
  238.         else if (a == &Nil<T>ListNode || !<T>EQ(a->hd, t->hd))
  239.           break;
  240.         else
  241.         {
  242.           a = a->tl;
  243.           t = t->tl;
  244.         }
  245.       }
  246.     }
  247.     p = p->tl;
  248.   }
  249.   return <T>List(&Nil<T>ListNode);
  250. }
  251.  
  252. int <T>List::contains(<T>List& target)
  253. {
  254.   <T>ListNode* targ = target.P;
  255.   if (targ == &Nil<T>ListNode)
  256.     return 0;
  257.  
  258.   <T>ListNode* p = P;
  259.   while (p != &Nil<T>ListNode)
  260.   {
  261.     if (<T>EQ(p->hd, targ->hd))
  262.     {
  263.       <T>ListNode* a = p->tl;
  264.       <T>ListNode* t = targ->tl;
  265.       for(;;)
  266.       {
  267.         if (t == &Nil<T>ListNode)
  268.           return 1;
  269.         else if (a == &Nil<T>ListNode || !<T>EQ(a->hd, t->hd))
  270.           break;
  271.         else
  272.         {
  273.           a = a->tl;
  274.           t = t->tl;
  275.         }
  276.       }
  277.     }
  278.     p = p->tl;
  279.   }
  280.   return 0;
  281. }
  282.  
  283. void <T>List::del(<T&> targ)
  284. {
  285.   <T>ListNode* h = P;
  286.   // Former bug: targ can be a reference to a element in this list
  287.   // So do not dereference a element if targ is the element,
  288.   // until targ is no longer needed, as dereferencing it may destroy it.
  289.   <T>ListNode* to_be_dereferenced = 0;
  290.  
  291.   for (;;)
  292.   {
  293.     if (h == &Nil<T>ListNode)
  294.     {
  295.       P = h;
  296.       if (to_be_dereferenced)
  297.     dereference(to_be_dereferenced);
  298.       return;
  299.     }
  300.     else if (<T>EQ(h->hd, targ))
  301.     {
  302.       <T>ListNode* nxt = h->tl;
  303.       reference(nxt);
  304.       if ((&targ == &h->hd) && (to_be_dereferenced == 0))
  305.     to_be_dereferenced = h;
  306.       else
  307.         dereference(h);
  308.       h = nxt;
  309.     }
  310.     else
  311.       break;
  312.   }
  313.  
  314.   <T>ListNode* trail = h;
  315.   <T>ListNode* p = h->tl;
  316.   while (p != &Nil<T>ListNode)
  317.   {
  318.     if (<T>EQ(p->hd, targ))
  319.     {
  320.       <T>ListNode* nxt = p->tl;
  321.       reference(nxt);
  322.       if ((&targ == &p->hd) && (to_be_dereferenced == 0))
  323.     to_be_dereferenced = p;
  324.       else
  325.         dereference(p);
  326.       trail->tl = nxt;
  327.       p = nxt;
  328.     }
  329.     else
  330.     {
  331.       trail = p;
  332.       p = p->tl;
  333.     }
  334.   }
  335.   P = h;
  336.   if (to_be_dereferenced)
  337.     dereference(to_be_dereferenced);
  338. }
  339.  
  340. void <T>List::del(<T>Predicate f)
  341. {
  342.   <T>ListNode* h = P;
  343.   for (;;)
  344.   {
  345.     if (h == &Nil<T>ListNode)
  346.     {
  347.       P = h;
  348.       return;
  349.     }
  350.     else if ((*f)(h->hd))
  351.     {
  352.       <T>ListNode* nxt = h->tl;
  353.       reference(nxt);
  354.       dereference(h);
  355.       h = nxt;
  356.     }
  357.     else
  358.       break;
  359.   }
  360.  
  361.   <T>ListNode* trail = h;
  362.   <T>ListNode* p = h->tl;
  363.   while (p != &Nil<T>ListNode)
  364.   {
  365.     if ((*f)(p->hd))
  366.     {
  367.       <T>ListNode* nxt = p->tl;
  368.       reference(nxt);
  369.       dereference(p);
  370.       trail->tl = nxt;
  371.       p = nxt;
  372.     }
  373.     else
  374.     {
  375.       trail = p;
  376.       p = p->tl;
  377.     }
  378.   }
  379.   P = h;
  380. }
  381.  
  382. void <T>List::select(<T>Predicate f)
  383. {
  384.   <T>ListNode* h = P;
  385.   for (;;)
  386.   {
  387.     if (h == &Nil<T>ListNode)
  388.     {
  389.       P = h;
  390.       return;
  391.     }
  392.     else if (!(*f)(h->hd))
  393.     {
  394.       <T>ListNode* nxt = h->tl;
  395.       reference(nxt);
  396.       dereference(h);
  397.       h = nxt;
  398.     }
  399.     else
  400.       break;
  401.   }
  402.   <T>ListNode* trail = h;
  403.   <T>ListNode* p = h->tl;
  404.   while (p != &Nil<T>ListNode)
  405.   {
  406.     if (!(*f)(p->hd))
  407.     {
  408.       <T>ListNode* nxt = p->tl;
  409.       reference(nxt);
  410.       dereference(p);
  411.       trail->tl = nxt;
  412.       p = nxt;
  413.     }
  414.     else
  415.     {
  416.       trail = p;
  417.       p = p->tl;
  418.     }
  419.   }
  420.   P = h;
  421. }
  422.  
  423. void <T>List::reverse()
  424. {
  425.   <T>ListNode* l = &Nil<T>ListNode;
  426.   <T>ListNode* p = P; 
  427.   while (p != &Nil<T>ListNode)
  428.   {
  429.     <T>ListNode* nxt = p->tl;
  430.     p->tl = l;
  431.     l = p;
  432.     p = nxt;
  433.   }
  434.   P = l;
  435. }
  436.  
  437.  
  438. <T>List copy(const <T>List& x)
  439. {
  440.   const <T>ListNode* a = x.P;
  441.   if (a == &Nil<T>ListNode)
  442.     return <T>List(&Nil<T>ListNode);
  443.   else
  444.   {
  445.     <T>ListNode* h = new<T>ListNode(a->hd);
  446.     <T>ListNode* trail = h;
  447.     for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  448.     {
  449.       <T>ListNode* n = new<T>ListNode(a->hd);
  450.       trail->tl = n;
  451.       trail = n;
  452.     }
  453.     trail->tl = &Nil<T>ListNode;
  454.     return <T>List(h);
  455.   }
  456. }
  457.  
  458.  
  459. <T>List subst(<T&> old, <T&> repl, <T>List& x)
  460. {
  461.   <T>ListNode* a = x.P;
  462.   if (a == &Nil<T>ListNode)
  463.     return <T>List(a);
  464.   else
  465.   {
  466.     <T>ListNode* h = new <T>ListNode;
  467.     h->ref = 1;
  468.     if (<T>EQ(a->hd, old))
  469.       h->hd = repl;
  470.     else
  471.       h->hd = a->hd;
  472.     <T>ListNode* trail = h;
  473.     for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  474.     {
  475.       <T>ListNode* n = new <T>ListNode;
  476.       n->ref = 1;
  477.       if (<T>EQ(a->hd, old))
  478.         n->hd = repl;
  479.       else
  480.         n->hd = a->hd;
  481.       trail->tl = n;
  482.       trail = n;
  483.     }
  484.     trail->tl = &Nil<T>ListNode;
  485.     return <T>List(h);
  486.   }
  487. }
  488.  
  489. <T>List combine(<T>Combiner f, <T>List& x, <T>List& y)
  490. {
  491.   <T>ListNode* a = x.P;
  492.   <T>ListNode* b = y.P;
  493.   if (a == &Nil<T>ListNode || b == &Nil<T>ListNode)
  494.     return <T>List(&Nil<T>ListNode);
  495.   else
  496.   {
  497.     <T>ListNode* h = new<T>ListNode((*f)(a->hd, b->hd));
  498.     <T>ListNode* trail = h;
  499.     a = a->tl;
  500.     b = b->tl;
  501.     while (a != &Nil<T>ListNode && b != &Nil<T>ListNode)
  502.     {
  503.       <T>ListNode* n = new<T>ListNode((*f)(a->hd, b->hd));
  504.       trail->tl = n;
  505.       trail = n;
  506.       a = a->tl;
  507.       b = b->tl;
  508.     }
  509.     trail->tl = &Nil<T>ListNode;
  510.     return <T>List(h);
  511.   }
  512. }
  513.  
  514. <T>List reverse(<T>List& x)
  515. {
  516.   <T>ListNode* a = x.P;
  517.   if (a == &Nil<T>ListNode)
  518.     return <T>List(a);
  519.   else
  520.   {
  521.     <T>ListNode* l = new<T>ListNode(a->hd);
  522.     l->tl = &Nil<T>ListNode;
  523.     for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  524.     {
  525.       <T>ListNode* n = new<T>ListNode(a->hd);
  526.       n->tl = l;
  527.       l = n;
  528.     }
  529.     return <T>List(l);
  530.   }
  531. }
  532.  
  533. <T>List append(<T>List& x, <T>List& y)
  534. {
  535.   <T>ListNode* a = x.P;
  536.   <T>ListNode* b = y.P;
  537.   reference(b);
  538.   if (a != &Nil<T>ListNode)
  539.   {
  540.     <T>ListNode* h = new<T>ListNode(a->hd);
  541.     <T>ListNode* trail = h;
  542.     for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  543.     {
  544.       <T>ListNode* n = new<T>ListNode(a->hd);
  545.       trail->tl = n;
  546.       trail = n;
  547.     }
  548.     trail->tl = b;
  549.     return <T>List(h);
  550.   }
  551.   else
  552.     return <T>List(b);
  553. }
  554.  
  555. void <T>List::prepend(<T>List& y)
  556. {
  557.   <T>ListNode* b = y.P;
  558.   if (b != &Nil<T>ListNode)
  559.   {
  560.     <T>ListNode* h = new<T>ListNode(b->hd);
  561.     <T>ListNode* trail = h;
  562.     for(b = b->tl; b != &Nil<T>ListNode; b = b->tl)
  563.     {
  564.       <T>ListNode* n = new<T>ListNode(b->hd);
  565.       trail->tl = n;
  566.       trail = n;
  567.     }
  568.     trail->tl = P;
  569.     P = h;
  570.   }
  571. }
  572.  
  573. <T>List concat(<T>List& x, <T>List& y)
  574. {
  575.   <T>ListNode* a = x.P;
  576.   <T>ListNode* b = y.P;
  577.   if (a != &Nil<T>ListNode)
  578.   {
  579.     <T>ListNode* h = new<T>ListNode(a->hd);
  580.     <T>ListNode* trail = h;
  581.     for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  582.     {
  583.       <T>ListNode* n = new<T>ListNode(a->hd);
  584.       trail->tl = n;
  585.       trail = n;
  586.     };
  587.     for(;b != &Nil<T>ListNode; b = b->tl)
  588.     {
  589.       <T>ListNode* n = new<T>ListNode(b->hd);
  590.       trail->tl = n;
  591.       trail = n;
  592.     }
  593.     trail->tl = &Nil<T>ListNode;
  594.     return <T>List(h);
  595.   }
  596.   else if (b != &Nil<T>ListNode)
  597.   {
  598.     <T>ListNode* h = new<T>ListNode(b->hd);
  599.     <T>ListNode* trail = h;
  600.     for(b = b->tl; b != &Nil<T>ListNode; b = b->tl)
  601.     {
  602.       <T>ListNode* n = new<T>ListNode(b->hd);
  603.       trail->tl = n;
  604.       trail = n;
  605.     }
  606.     trail->tl = &Nil<T>ListNode;
  607.     return <T>List(h);
  608.   }
  609.   else
  610.     return <T>List(&Nil<T>ListNode);
  611. }
  612.  
  613. <T>List select(<T>Predicate f, <T>List& x)
  614. {
  615.   <T>ListNode* a = x.P;
  616.   <T>ListNode* h = &Nil<T>ListNode;
  617.   while (a != &Nil<T>ListNode)
  618.   {
  619.     if ((*f)(a->hd))
  620.     {
  621.       h = new<T>ListNode(a->hd);
  622.       <T>ListNode* trail = h;
  623.       for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  624.       {
  625.         if ((*f)(a->hd))
  626.         {
  627.           <T>ListNode* n = new<T>ListNode(a->hd);
  628.           trail->tl = n;
  629.           trail = n;
  630.         }
  631.       }
  632.       trail->tl = &Nil<T>ListNode;
  633.       break;
  634.     }
  635.     else
  636.       a = a->tl;
  637.   }
  638.   return <T>List(h);
  639. }
  640.  
  641. <T>List remove(<T>Predicate f, <T>List& x)
  642. {
  643.   <T>ListNode* a = x.P;
  644.   <T>ListNode* h = &Nil<T>ListNode;
  645.   while (a != &Nil<T>ListNode)
  646.   {
  647.     if (!(*f)(a->hd))
  648.     {
  649.       h = new<T>ListNode(a->hd);
  650.       <T>ListNode* trail = h;
  651.       for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  652.       {
  653.         if (!(*f)(a->hd))
  654.         {
  655.           <T>ListNode* n = new<T>ListNode(a->hd);
  656.           trail->tl = n;
  657.           trail = n;
  658.         }
  659.       }
  660.       trail->tl = &Nil<T>ListNode;
  661.       break;
  662.     }
  663.     else
  664.       a = a->tl;
  665.   }
  666.   return <T>List(h);
  667. }
  668.  
  669. <T>List remove(<T&> targ, <T>List& x)
  670. {
  671.   <T>ListNode* a = x.P;
  672.   <T>ListNode* h = &Nil<T>ListNode;
  673.   while (a != &Nil<T>ListNode)
  674.   {
  675.     if (!(<T>EQ(a->hd, targ)))
  676.     {
  677.       h = new<T>ListNode(a->hd);
  678.       <T>ListNode* trail = h;
  679.       for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  680.       {
  681.         if (!<T>EQ(a->hd, targ))
  682.         {
  683.           <T>ListNode* n = new<T>ListNode(a->hd);
  684.           trail->tl = n;
  685.           trail = n;
  686.         }
  687.       }
  688.       trail->tl = &Nil<T>ListNode;
  689.       break;
  690.     }
  691.     else
  692.       a = a->tl;
  693.   }
  694.   return <T>List(h);
  695. }
  696.  
  697. <T>List map(<T>Mapper f, <T>List& x)
  698. {
  699.   <T>ListNode* a = x.P;
  700.   <T>ListNode* h = &Nil<T>ListNode;
  701.   if (a != &Nil<T>ListNode)
  702.   {
  703.     h = new<T>ListNode((*f)(a->hd));
  704.     <T>ListNode* trail = h;
  705.     for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  706.     {
  707.       <T>ListNode* n = new<T>ListNode((*f)(a->hd));
  708.       trail->tl = n;
  709.       trail = n;
  710.     }
  711.     trail->tl = &Nil<T>ListNode;
  712.   }
  713.   return <T>List(h);
  714. }
  715.  
  716.  
  717. <T>List merge(<T>List& x, <T>List& y, <T>Comparator f)
  718. {
  719.   <T>ListNode* a = x.P;
  720.   <T>ListNode* b = y.P;
  721.  
  722.   if (a == &Nil<T>ListNode)
  723.   {
  724.     if (b == &Nil<T>ListNode)
  725.       return <T>List(&Nil<T>ListNode);
  726.     else
  727.       return copy(y);
  728.   }
  729.   else if (b == &Nil<T>ListNode)
  730.     return copy(x);
  731.  
  732.   <T>ListNode* h = new <T>ListNode;
  733.   h->ref = 1;
  734.   if ((*f)(a->hd, b->hd) <= 0)
  735.   {
  736.     h->hd = a->hd;
  737.     a = a->tl;
  738.   }
  739.   else
  740.   {
  741.     h->hd = b->hd;
  742.     b = b->tl;
  743.   }
  744.  
  745.   <T>ListNode* r = h;
  746.  
  747.   for(;;)
  748.   {
  749.     if (a == &Nil<T>ListNode)
  750.     {
  751.       while (b != &Nil<T>ListNode)
  752.       {
  753.         <T>ListNode* n = new <T>ListNode;
  754.         n->ref = 1;
  755.         n->hd = b->hd;
  756.         r->tl = n;
  757.         r = n;
  758.         b = b->tl;
  759.       }
  760.       r->tl = &Nil<T>ListNode;
  761.       return <T>List(h);
  762.     }
  763.     else if (b == &Nil<T>ListNode)
  764.     {
  765.       while (a != &Nil<T>ListNode)
  766.       {
  767.         <T>ListNode* n = new <T>ListNode;
  768.         n->ref = 1;
  769.         n->hd = a->hd;
  770.         r->tl = n;
  771.         r = n;
  772.         a = a->tl;
  773.       }
  774.       r->tl = &Nil<T>ListNode;
  775.       return <T>List(h);
  776.     }
  777.     else if ((*f)(a->hd, b->hd) <= 0)
  778.     {
  779.       <T>ListNode* n = new <T>ListNode;
  780.       n->ref = 1;
  781.       n->hd = a->hd;
  782.       r->tl = n;
  783.       r = n;
  784.       a = a->tl;
  785.     }
  786.     else
  787.     {
  788.       <T>ListNode* n = new <T>ListNode;
  789.       n->ref = 1;
  790.       n->hd = b->hd;
  791.       r->tl = n;
  792.       r = n;
  793.       b = b->tl;
  794.     }
  795.   }
  796. }
  797.  
  798. void <T>List::sort(<T>Comparator f)
  799. {
  800.   // strategy: place runs in queue, merge runs until done
  801.   // This is often very fast
  802.  
  803.   if (P == &Nil<T>ListNode || P->tl == &Nil<T>ListNode)
  804.     return;
  805.  
  806.   int qlen = 250;   // guess a good queue size, realloc if necessary
  807.  
  808.   <T>ListNode** queue = (<T>ListNode**)malloc(qlen * sizeof(<T>ListNode*));
  809.  
  810.   <T>ListNode* h = P;
  811.   <T>ListNode* a = h;
  812.   <T>ListNode* b = a->tl;
  813.   int qin = 0;
  814.  
  815.   while (b != &Nil<T>ListNode)
  816.   {
  817.     if ((*f)(a->hd, b->hd) > 0)
  818.     {
  819.       if (h == a)               // minor optimization: ensure runlen >= 2
  820.       {
  821.         h = b;
  822.         a->tl = b->tl;
  823.         b->tl = a;
  824.         b = a->tl;
  825.       }
  826.       else
  827.       {
  828.         if (qin >= qlen)
  829.         {
  830.           qlen *= 2;
  831.           queue = (<T>ListNode**)realloc(queue, qlen * sizeof(<T>ListNode*));
  832.         }
  833.         queue[qin++] = h;
  834.         a->tl = &Nil<T>ListNode;
  835.         h = a = b;
  836.         b = b->tl;
  837.       }
  838.     }
  839.     else
  840.     {
  841.       a = b;
  842.       b = b->tl;
  843.     }
  844.   }
  845.  
  846.   int count = qin;
  847.   queue[qin] = h;
  848.   if (++qin >= qlen) qin = 0;
  849.   int qout = 0;
  850.  
  851.   while (count-- > 0)
  852.   {
  853.     a = queue[qout];
  854.     if (++qout >= qlen) qout = 0;
  855.     b = queue[qout];
  856.     if (++qout >= qlen) qout = 0;
  857.  
  858.     if ((*f)(a->hd, b->hd) <= 0)
  859.     {
  860.       h = a;
  861.       a = a->tl;
  862.     }
  863.     else
  864.     {
  865.       h = b;
  866.       b = b->tl;
  867.     }
  868.     queue[qin] = h;
  869.     if (++qin >= qlen) qin = 0;
  870.  
  871.     for (;;)
  872.     {
  873.       if (a == &Nil<T>ListNode)
  874.       {
  875.         h->tl = b;
  876.         break;
  877.       }
  878.       else if (b == &Nil<T>ListNode)
  879.       {
  880.         h->tl = a;
  881.         break;
  882.       }
  883.       else if ((*f)(a->hd, b->hd) <= 0)
  884.       {
  885.         h->tl = a;
  886.         h = a;
  887.         a = a->tl;
  888.       }
  889.       else
  890.       {
  891.         h->tl = b;
  892.         h = b;
  893.         b = b->tl;
  894.       }
  895.     }
  896.   }
  897.   P = queue[qout];
  898.   free(queue);
  899. }
  900.     
  901. int <T>List::list_length()
  902. {
  903.   <T>ListNode* fast = P;
  904.   if (fast == &Nil<T>ListNode)
  905.     return 0;
  906.  
  907.   <T>ListNode* slow = fast->tl;
  908.   if (slow == &Nil<T>ListNode)
  909.     return 1;
  910.  
  911.   fast = slow->tl;
  912.   int n = 2;
  913.  
  914.   for (;;)
  915.   {
  916.     if (fast == &Nil<T>ListNode)
  917.       return n;
  918.     else if (fast->tl == &Nil<T>ListNode)
  919.       return n+1;
  920.     else if (fast == slow)
  921.       return -1;
  922.     else
  923.     {
  924.       n += 2;
  925.       fast = fast->tl->tl;
  926.       slow = slow->tl;
  927.     }
  928.   }
  929. }
  930.  
  931. void <T>List::error(const char* msg)
  932. {
  933.   (*lib_error_handler)("List", msg);
  934. }
  935.  
  936. int <T>List::OK()
  937. {
  938.   int v = P != 0;               // have a node
  939.   // check that all nodes OK, even if circular:
  940.  
  941.   <T>ListNode* fast = P;
  942.   if (fast != &Nil<T>ListNode)
  943.   {
  944.     v &= fast->ref != 0;
  945.     <T>ListNode* slow = fast->tl;
  946.     v &= slow->ref != 0;
  947.     if (v && slow != &Nil<T>ListNode)
  948.     {
  949.       fast = slow->tl;
  950.       v &= fast->ref != 0;
  951.       while (v)
  952.       {
  953.         if (fast == &Nil<T>ListNode)
  954.           break;
  955.         else if (fast->tl == &Nil<T>ListNode)
  956.           break;
  957.         else if (fast == slow)
  958.           break;
  959.         else
  960.         {
  961.           v &= fast->ref != 0 && slow->ref != 0;
  962.           fast = fast->tl->tl;
  963.           slow = slow->tl;
  964.         }
  965.       }
  966.     }
  967.   }
  968.   if (!v) error ("invariant failure");
  969.   return v;
  970. }
  971.